{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subsequence With the Minimum Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少得分子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以从字符串 <code>t</code>&nbsp;中删除任意数目的字符。</p>\n",
    "\n",
    "<p>如果没有从字符串&nbsp;<code>t</code>&nbsp;中删除字符，那么得分为&nbsp;<code>0</code>&nbsp;，否则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>left</code>&nbsp;为删除字符中的最小下标。</li>\n",
    "\t<li>令&nbsp;<code>right</code>&nbsp;为删除字符中的最大下标。</li>\n",
    "</ul>\n",
    "\n",
    "<p>字符串的得分为&nbsp;<code>right - left + 1</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回使<em>&nbsp;</em><code>t</code><em> </em>成为<em>&nbsp;</em><code>s</code>&nbsp;子序列的最小得分。</p>\n",
    "\n",
    "<p>一个字符串的 <strong>子序列</strong>&nbsp;是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说&nbsp;<code>\"ace\"</code> 是&nbsp;<code>\"<strong><em>a</em></strong>b<strong><em>c</em></strong>d<strong><em>e</em></strong>\"</code>&nbsp;的子序列，但是&nbsp;<code>\"aec\"</code>&nbsp;不是）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abacaba\", t = \"bzaa\"\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>这个例子中，我们删除下标 1 处的字符 \"z\" （下标从 0 开始）。\n",
    "字符串 t 变为 \"baa\" ，它是字符串 \"abacaba\" 的子序列，得分为 1 - 1 + 1 = 1 。\n",
    "1 是能得到的最小得分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"cde\", t = \"xyz\"\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>这个例子中，我们将下标为 0， 1 和 2 处的字符 \"x\" ，\"y\" 和 \"z\" 删除（下标从 0 开始）。\n",
    "字符串变成 \"\" ，它是字符串 \"cde\" 的子序列，得分为 2 - 0 + 1 = 3 。\n",
    "3 是能得到的最小得分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;都只包含小写英文字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subsequence-with-the-minimum-score](https://leetcode.cn/problems/subsequence-with-the-minimum-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subsequence-with-the-minimum-score](https://leetcode.cn/problems/subsequence-with-the-minimum-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abacaba\"\\n\"bzaa\"', '\"cde\"\\n\"xyz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        lenT, lenS = len(t), len(s)\n",
    "        inf = float('inf')\n",
    "        rightOffs = [float('-inf')]*lenT\n",
    "        leftOff, rightOff = 0, lenT - 1\n",
    "        for r in range(lenS-1, -1, -1):\n",
    "            if s[r] == t[rightOff]:\n",
    "                rightOffs[rightOff] = r\n",
    "                rightOff -= 1\n",
    "                if rightOff < 0: break\n",
    "        r = res = bisect_left(rightOffs, 0)\n",
    "        leftOff = 0\n",
    "        for l, cS in enumerate(s):\n",
    "            if cS != t[leftOff]: continue\n",
    "            r = bisect_left(rightOffs, l+1, r)\n",
    "            if r - leftOff - 1 <= 0: return 0\n",
    "            res = min(res, r - leftOff - 1)\n",
    "            leftOff += 1\n",
    "            if leftOff == lenT: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        '''\n",
    "        可以直接考虑在t中删除一段子数组，剩下的被分为了t的头和尾两个部分\n",
    "        然后考虑将s也分为两个部分，s[:i]和s[i:] i从1到n\n",
    "        如果t的头和尾两个部分分别都出现在了s的前缀和后缀中，那么这种分割就是合法的\n",
    "\n",
    "        更进一步地，我们考虑直接枚举s中的分割点i\n",
    "        在s[:i]中，尽可能地匹配t的前缀，直到出现匹配不了的情况，记录下标为pre\n",
    "        在s[i:]中，尽可能地匹配t的后缀，直到出现匹配不了的情况，记录下标为last\n",
    "        更新ans为last-pre+1，注意，如果ans为负数，直接记为0并退出循环即可\n",
    "        实际实现的时候，每成功匹配一次pre+1，last同理-1\n",
    "\n",
    "        '''\n",
    "        n=len(t)\n",
    "        pre,last=0,n-1\n",
    "        cnt=[0]*len(s)\n",
    "        #首先记录s[0:]中\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if last>=0 and s[i]==t[last]:last-=1\n",
    "            cnt[i]=last\n",
    "        #如何预处理出s的后缀能够处理的t的后缀的最远下标呢\n",
    "        ans=last-pre+1\n",
    "        #逐渐增加pre和last\n",
    "        for i in range(0,len(s)):\n",
    "            if pre<n and s[i]==t[pre]:\n",
    "                pre+=1\n",
    "            if i+1<len(s):last=cnt[i+1]\n",
    "            ans=min(last-pre+1,ans)\n",
    "        return 0 if ans<0 else ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # n,m=len(s),len(t)\n",
    "        # suf=[m]*(n+1)\n",
    "        # j=m-1\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     if j>=0 and s[i]==t[j]:\n",
    "        #         j-=1\n",
    "        #     suf[i]=j+1\n",
    "        # ans=suf[0]\n",
    "        # if ans==0:return 0\n",
    "\n",
    "        # j=0\n",
    "        # for i,c in enumerate(s):\n",
    "        #     if c==t[j]:\n",
    "        #         j+=1\n",
    "        #         ans=min(ans,suf[i+1]-j)\n",
    "        # return ans\n",
    "        n,m=len(s),len(t)\n",
    "        suf=[m]*(n+1)\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                j-=1\n",
    "            suf[i]=j+1\n",
    "        ans=suf[0]\n",
    "        if ans==0:return 0\n",
    "\n",
    "        j=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c==t[j]:\n",
    "                j+=1\n",
    "                ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m=len(s),len(t)\n",
    "        suf=[m]*(n+1)\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                j-=1\n",
    "            suf[i]=j+1\n",
    "        ans=suf[0]\n",
    "        if ans==0:return 0\n",
    "\n",
    "        j=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c==t[j]:\n",
    "                j+=1\n",
    "                ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n+1)\n",
    "        j = m - 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j >=0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        \n",
    "        j = 0\n",
    "        for i, x in enumerate(s):\n",
    "            if x == t[j]:\n",
    "                j += 1\n",
    "                ans = min(suf[i+1]-j, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        suf = [m]*(n+1)\n",
    "        j = m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j >= 0 and t[j]==s[i]:\n",
    "                j -= 1\n",
    "            suf[i] = j+1\n",
    "        j = 0\n",
    "        ans = suf[0]\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        for i,x in enumerate(s):\n",
    "            if t[j] == s[i]:\n",
    "                j += 1\n",
    "                ans = min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # 如果只删除一个left,right相同\n",
    "        # 注意题目说的是最小得分，能删一个尽量删一个\n",
    "        # 不能用删一个解决，删除的要尽量相邻且length尽量小\n",
    "        # 按照题目要求分析，right应该是从左往右找\n",
    "        # “aabcabb”   \"cbca\"   # 找 完全不同的字母优先删除，如果有两个，那么字母之间的就也能完全删除了，因为删除这些不会对结果造成任何影响\n",
    "        # 只有一个那就从左右开始删除，因为删除任意两个距离的字母，中间的字母一定是能删除的\n",
    "        # 如果没有呢？\n",
    "        # “aaabb”   \"bbaaa\"\n",
    "\n",
    "        # 无论怎么样， 肯定是要统计个数， t中一旦有超过或不符合的情况就是要删除的\n",
    "        # 从t中找不符合情况的，然后删除，然后再去和s匹配，如果发现不符合，我们又要考虑左右的最小值，这样思考就显得十分的复杂\n",
    "        # 因此，我们应该从s上考虑\n",
    "        # 因为s是不变的，那么我们就可以用一条分割线去分割s，当我们把s枚举不同的分割线去分割，然后匹配t，s前缀能匹配多少t的前缀， s的后缀能匹配 t 的多少后缀，那么我们去匹配最多的那条分割线的情况，就可以把结果求出来了，然后因为是对s的分割线进行枚举，所以时间的复杂度也就是O(n) \n",
    "\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "\n",
    "        # 枚举s的分割线  --- s的分割线是right的终点 那么left的终点就是i-1\n",
    "        # 如果每次换分割线的时候都重新去匹配一次，那么结果还是o(n方)\n",
    "        # 这里我们就需要用到前后缀，我们先把所有的s的后缀都匹配一遍\n",
    "        # 然后我们再把所有的前缀都匹配一遍\n",
    "        # 最后我们就只需要根据分割线，观察前缀和后缀的匹配情况，就能得出答案\n",
    "        # 由于最后剩下来的一定是一个区间，所以最后答案的计算也是非常方便的\n",
    "\n",
    "        # 匹配后缀  -- 记录索引\n",
    "        surf = [m] * (n + 1)\n",
    "        t_right = m - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if t_right>=0 and s[i] == t[t_right]:\n",
    "                t_right -= 1\n",
    "            surf[i] = t_right + 1\n",
    "        \n",
    "        # 匹配前缀  -- 记录索引，在匹配前缀的同时计算答案 \n",
    "        res = surf[0]\n",
    "        if res == 0: return 0\n",
    "        t_left = 0\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == t[t_left]:\n",
    "                t_left += 1\n",
    "                res = min(res, surf[i] - t_left)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "\n",
    "            n = len(s)\n",
    "            m = len(t)\n",
    "            suf = [m] * (n+1)\n",
    "            j = m - 1\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if j>=0 and s[i] == t[j]:\n",
    "                    j -= 1\n",
    "                suf[i] = j + 1\n",
    "            j = 0;ans = suf[0]\n",
    "            for i,x in enumerate(s):\n",
    "                if t[j] == x:\n",
    "                    j += 1\n",
    "                    if suf[i+1] >= j:\n",
    "                        ans = min(ans,suf[i+1] - j)\n",
    "                    if j == m:\n",
    "                        break\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        suf = [m]*(n+1)\n",
    "        j = m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j+1\n",
    "        ans = suf[0]\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        j = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                ans = min(ans,suf[i+1]-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # n,m=len(s),len(t)\n",
    "        # suf=[m]*(n+1)\n",
    "        # j=m-1\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     if j>=0 and s[i]==t[j]:\n",
    "        #         j-=1\n",
    "        #     suf[i]=j+1\n",
    "        # ans=suf[0]\n",
    "        # if ans==0:return 0\n",
    "\n",
    "        # j=0\n",
    "        # for i,c in enumerate(s):\n",
    "        #     if c==t[j]:\n",
    "        #         j+=1\n",
    "        #         ans=min(ans,suf[i+1]-j)\n",
    "        # return ans\n",
    "        n,m=len(s),len(t)\n",
    "        suf=[m]*(n+1)\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                j-=1\n",
    "            suf[i]=j+1\n",
    "        ans=suf[0]\n",
    "        if ans==0:return 0\n",
    "\n",
    "        j=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c==t[j]:\n",
    "                j+=1\n",
    "                ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # 如果只删除一个left,right相同\n",
    "        # 注意题目说的是最小得分，能删一个尽量删一个\n",
    "        # 不能用删一个解决，删除的要尽量相邻且length尽量小\n",
    "        # 按照题目要求分析，right应该是从左往右找\n",
    "        # “aabcabb”   \"cbca\"   # 找 完全不同的字母优先删除，如果有两个，那么字母之间的就也能完全删除了，因为删除这些不会对结果造成任何影响\n",
    "        # 只有一个那就从左右开始删除，因为删除任意两个距离的字母，中间的字母一定是能删除的\n",
    "        # 如果没有呢？\n",
    "        # “aaabb”   \"bbaaa\"\n",
    "\n",
    "        # 无论怎么样， 肯定是要统计个数， t中一旦有超过或不符合的情况就是要删除的\n",
    "        # 从t中找不符合情况的，然后删除，然后再去和s匹配，如果发现不符合，我们又要考虑左右的最小值，这样思考就显得十分的复杂\n",
    "        # 因此，我们应该从s上考虑\n",
    "        # 因为s是不变的，那么我们就可以用一条分割线去分割s，当我们把s枚举不同的分割线去分割，然后匹配t，s前缀能匹配多少t的前缀， s的后缀能匹配 t 的多少后缀，那么我们去匹配最多的那条分割线的情况，就可以把结果求出来了，然后因为是对s的分割线进行枚举，所以时间的复杂度也就是O(n) \n",
    "\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "\n",
    "        # 枚举s的分割线  --- s的分割线是right的终点 那么left的终点就是i-1\n",
    "        # 如果每次换分割线的时候都重新去匹配一次，那么结果还是o(n方)\n",
    "        # 这里我们就需要用到前后缀，我们先把所有的s的后缀都匹配一遍\n",
    "        # 然后我们再把所有的前缀都匹配一遍\n",
    "        # 最后我们就只需要根据分割线，观察前缀和后缀的匹配情况，就能得出答案\n",
    "        # 由于最后剩下来的一定是一个区间，所以最后答案的计算也是非常方便的\n",
    "\n",
    "        # 匹配后缀  -- 记录索引\n",
    "        surf = [m] * (n + 1)\n",
    "        t_right = m - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if t_right>=0 and s[i] == t[t_right]:\n",
    "                t_right -= 1\n",
    "            surf[i] = t_right + 1\n",
    "        \n",
    "        # 匹配前缀  -- 记录索引，在匹配前缀的同时计算答案 \n",
    "        res = surf[0]\n",
    "        if res == 0: return 0\n",
    "        t_left = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == t[t_left]:\n",
    "                t_left += 1\n",
    "                res = min(res, surf[i+1] - t_left)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # 如果只删除一个left,right相同\n",
    "        # 注意题目说的是最小得分，能删一个尽量删一个\n",
    "        # 不能用删一个解决，删除的要尽量相邻且length尽量小\n",
    "        # 按照题目要求分析，right应该是从左往右找\n",
    "        # “aabcabb”   \"cbca\"   # 找 完全不同的字母优先删除，如果有两个，那么字母之间的就也能完全删除了，因为删除这些不会对结果造成任何影响\n",
    "        # 只有一个那就从左右开始删除，因为删除任意两个距离的字母，中间的字母一定是能删除的\n",
    "        # 如果没有呢？\n",
    "        # “aaabb”   \"bbaaa\"\n",
    "\n",
    "        # 无论怎么样， 肯定是要统计个数， t中一旦有超过或不符合的情况就是要删除的\n",
    "        # 从t中找不符合情况的，然后删除，然后再去和s匹配，如果发现不符合，我们又要考虑左右的最小值，这样思考就显得十分的复杂\n",
    "        # 因此，我们应该从s上考虑\n",
    "        # 因为s是不变的，那么我们就可以用一条分割线去分割s，当我们把s枚举不同的分割线去分割，然后匹配t，s前缀能匹配多少t的前缀， s的后缀能匹配 t 的多少后缀，那么我们去匹配最多的那条分割线的情况，就可以把结果求出来了，然后因为是对s的分割线进行枚举，所以时间的复杂度也就是O(n) \n",
    "\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "\n",
    "        # 枚举s的分割线  --- s的分割线是right的终点 那么left的终点就是i-1\n",
    "        # 如果每次换分割线的时候都重新去匹配一次，那么结果还是o(n方)\n",
    "        # 这里我们就需要用到前后缀，我们先把所有的s的后缀都匹配一遍\n",
    "        # 然后我们再把所有的前缀都匹配一遍\n",
    "        # 最后我们就只需要根据分割线，观察前缀和后缀的匹配情况，就能得出答案\n",
    "        # 由于最后剩下来的一定是一个区间，所以最后答案的计算也是非常方便的\n",
    "\n",
    "        # 匹配后缀  -- 记录索引\n",
    "        surf = [m] * (n + 1)\n",
    "        t_right = m - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if t_right>=0 and s[i] == t[t_right]:\n",
    "                t_right -= 1\n",
    "            surf[i] = t_right + 1\n",
    "        \n",
    "        # 匹配前缀  -- 记录索引，在匹配前缀的同时计算答案 \n",
    "        res = surf[0]\n",
    "        if res == 0: return 0\n",
    "        t_left = 0\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == t[t_left]:\n",
    "                t_left += 1\n",
    "            res = min(res, surf[i] - t_left)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        # 如果只删除一个left,right相同\n",
    "        # 注意题目说的是最小得分，能删一个尽量删一个\n",
    "        # 不能用删一个解决，删除的要尽量相邻且length尽量小\n",
    "        # 按照题目要求分析，right应该是从左往右找\n",
    "        # “aabcabb”   \"cbca\"   # 找 完全不同的字母优先删除，如果有两个，那么字母之间的就也能完全删除了，因为删除这些不会对结果造成任何影响\n",
    "        # 只有一个那就从左右开始删除，因为删除任意两个距离的字母，中间的字母一定是能删除的\n",
    "        # 如果没有呢？\n",
    "        # “aaabb”   \"bbaaa\"\n",
    "\n",
    "        # 无论怎么样， 肯定是要统计个数， t中一旦有超过或不符合的情况就是要删除的\n",
    "        # 从t中找不符合情况的，然后删除，然后再去和s匹配，如果发现不符合，我们又要考虑左右的最小值，这样思考就显得十分的复杂\n",
    "        # 因此，我们应该从s上考虑\n",
    "        # 因为s是不变的，那么我们就可以用一条分割线去分割s，当我们把s枚举不同的分割线去分割，然后匹配t，s前缀能匹配多少t的前缀， s的后缀能匹配 t 的多少后缀，那么我们去匹配最多的那条分割线的情况，就可以把结果求出来了，然后因为是对s的分割线进行枚举，所以时间的复杂度也就是O(n) \n",
    "\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "\n",
    "        # 枚举s的分割线  --- s的分割线是right的终点 那么left的终点就是i-1\n",
    "        # 如果每次换分割线的时候都重新去匹配一次，那么结果还是o(n方)\n",
    "        # 这里我们就需要用到前后缀，我们先把所有的s的后缀都匹配一遍\n",
    "        # 然后我们再把所有的前缀都匹配一遍\n",
    "        # 最后我们就只需要根据分割线，观察前缀和后缀的匹配情况，就能得出答案\n",
    "        # 由于最后剩下来的一定是一个区间，所以最后答案的计算也是非常方便的\n",
    "\n",
    "        # 匹配后缀  -- 记录索引\n",
    "        surf = [m] * (n + 1)\n",
    "        t_right = m - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if t_right>=0 and s[i] == t[t_right]:\n",
    "                t_right -= 1\n",
    "            surf[i] = t_right + 1\n",
    "        \n",
    "        # 匹配前缀  -- 记录索引，在匹配前缀的同时计算答案 \n",
    "        res = surf[0]\n",
    "        if res == 0: return 0\n",
    "        t_left = 0\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == t[t_left]:\n",
    "                t_left += 1\n",
    "            res = min(res, surf[i] - t_left)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        suf = [m] * (n+1)\n",
    "        j = m - 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        \n",
    "        ans = suf[0]\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        \n",
    "        j = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                ans = min(ans,suf[i+1] - j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n1, n2 = len(s), len(t)\n",
    "        right = [n2] * (n1 + 1)\n",
    "        idx = n2 - 1\n",
    "        for i in range(n1 - 1, - 1, - 1):\n",
    "            if idx >= 0 and s[i] == t[idx]:\n",
    "                idx -= 1 \n",
    "            right[i] = idx + 1\n",
    "        res = right[0]\n",
    "        if res == 0:\n",
    "            return 0\n",
    "        idx = 0\n",
    "        for i in range(n1):\n",
    "            if idx < n2 and s[i] == t[idx]:\n",
    "                idx += 1 \n",
    "            res = min(res, right[i + 1] - idx)\n",
    "        return res \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        \n",
    "        res = suf[0]\n",
    "\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if j < m and s[i] == t[j]:\n",
    "                j += 1\n",
    "            if suf[i + 1] >= j:\n",
    "                res = min(res, suf[i + 1] - j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        '''\n",
    "        有思路后借助样例分析代码应该i如何实现\n",
    "        suf[i]表示s[i:]能够匹配t[suf[i]:]\n",
    "\n",
    "        '''\n",
    "\n",
    "        n=len(s)\n",
    "        m=len(t)\n",
    "        suf=[m]*(n+1) #有些数组开+1很有好处，特别是一些对于下标有+1和-1需求的\n",
    "        #双指针j\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                suf[i]=j  \n",
    "                j-=1\n",
    "            suf[i]=j+1  \n",
    "        ans=suf[0]  #借助样例得到的结论\n",
    "        if ans==0: return 0  \n",
    "        j=0 #枚举前缀\n",
    "        for i,c in enumerate(s):\n",
    "            if c==t[j]: #j=m代表了t就是s的子序列，这在上面已经判断过了\n",
    "                j+=1\n",
    "                ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "\n",
    "        '''\n",
    "        二分写法有点太复杂了，一时半会解决不好，很容易写不出来\n",
    "        '''\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n+1)\n",
    "        j = m - 1\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and t[j] == s[i]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        \n",
    "        ans = suf[0]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i+1] - j)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        #得分是区间长度，针对某个区间，删除区间的一部分和删除区间所有元素的得分一致\n",
    "        #删除的是子串\n",
    "        m,n=len(t),len(s)\n",
    "        #后缀，定义suf为s对应t的最长后缀开始下标\n",
    "        suf=[m for _ in range(n+1)]\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                j-=1\n",
    "            suf[i]=j+1\n",
    "        if suf[0]==0:\n",
    "            return 0\n",
    "        ans=suf[0]\n",
    "        j=0\n",
    "        for i in range(n):\n",
    "            if j<m and s[i]==t[j]:\n",
    "                j+=1\n",
    "            # 删除的是t里的字符，所以suf[i]对应的是t内的元素位置\n",
    "            ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        suf = [m]*(n+1)\n",
    "        j = m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j+1\n",
    "        ans = suf[0]\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        j = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                ans = min(ans,suf[i+1]-j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        ans = suf[0]  # 删除 t[:suf[0]]\n",
    "        if ans == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == t[j]:  # 注意 j 不会等于 m，因为上面 suf[0]>0 表示 t 不是 s 的子序列\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)  # 删除 t[j:suf[i+1]]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m, n = len(s), len(t)\n",
    "        # prefix = [m] * n\n",
    "        # suffix = [-1] * n\n",
    "        # left, right = -1, -1\n",
    "        # j = 0\n",
    "        # for i in range(n):\n",
    "        #     while j < m and t[i] != s[j]:\n",
    "        #         j += 1\n",
    "        #     if j == m:\n",
    "        #         left = i\n",
    "        #         break\n",
    "        #     prefix[i] = j\n",
    "        #     j += 1\n",
    "        # j = m - 1\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     while j > -1 and s[j] != t[i]:\n",
    "        #         j -= 1\n",
    "        #     if j == -1:\n",
    "        #         right = i\n",
    "        #         break\n",
    "        #     suffix[i] = j\n",
    "        #     j -= 1\n",
    "        # ans = inf    \n",
    "        # for i in range(left):\n",
    "        #     j = bisect_left(suffix, prefix[i] + 1)\n",
    "        #     if ans >  j - i - 1:\n",
    "        #         ans = j - i - 1\n",
    "        # ans = min(ans, n - left, right + 1)\n",
    "        # return ans if ans < inf else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        suf = [m] * (n + 1)\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j + 1\n",
    "        if suf[0] == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = suf[0]\n",
    "        j = 0 + int(s[0] == t[0])\n",
    "        for i in range(1, n):\n",
    "            if s[i] == t[j]:\n",
    "                j += 1\n",
    "                ans = min(ans, suf[i + 1] - j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "\n",
    "        right = [n] * (m+1)\n",
    "        j = n - 1\n",
    "        for i in range(m-1,-1,-1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "\n",
    "            right[i] = j + 1\n",
    "\n",
    "        res = right[0]\n",
    "        if res == 0: return 0\n",
    "\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            if s[i] == t[j]:\n",
    "                j += 1\n",
    "                res = min(res, right[i+1] - j)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m=len(s),len(t)\n",
    "        left,right=[0]*(n+1),[0]*(n+1)\n",
    "        j = 0\n",
    "        cnt = 0\n",
    "        for k in range(n):\n",
    "            if j < m and s[k] == t[j]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            left[k+1] = cnt\n",
    "        \n",
    "        cnt = 0\n",
    "        j = m - 1\n",
    "        for k in range(n-1,-1,-1):\n",
    "            if j >= 0 and s[k] == t[j]:\n",
    "                j -= 1\n",
    "                cnt += 1\n",
    "            right[k] = cnt\n",
    "        \n",
    "        ans = m\n",
    "        for i in range(n+1):\n",
    "            ans = min(ans,max(0,m - (left[i] + right[i])))\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        sn = len(s)\n",
    "        tn = len(t)\n",
    "        l = [inf] * tn\n",
    "        # l[0] = 0\n",
    "        j = 0\n",
    "        for i in range(sn):\n",
    "            if j < tn and s[i] == t[j]:\n",
    "                l[j] = i\n",
    "                j += 1\n",
    "        r = [inf] * tn\n",
    "        \n",
    "        j = tn - 1\n",
    "        for i in range(sn - 1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                r[j] = i\n",
    "                # print(j, i)\n",
    "                j -= 1\n",
    "                \n",
    "        j = 0\n",
    "        # print(l, r)\n",
    "        ans = inf\n",
    "        while j < tn and r[j] == inf:\n",
    "            j += 1\n",
    "        ans = j\n",
    "        # print(ans)\n",
    "        for i in range(tn):\n",
    "            if l[i] == inf: continue\n",
    "            while j < tn and (r[j] == inf or r[j] <= l[i]):\n",
    "                j += 1\n",
    "            # print(j, i)\n",
    "            ans = min(ans, max(0, j - i - 1))\n",
    "        return ans\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        prefix = [m] * n\n",
    "        suffix = [-1] * n\n",
    "        left, right = -1, -1\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j < m and t[i] != s[j]:\n",
    "                j += 1\n",
    "            if j == m:\n",
    "                left = i\n",
    "                break\n",
    "            prefix[i] = j\n",
    "            j += 1\n",
    "        j = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while j > -1 and s[j] != t[i]:\n",
    "                j -= 1\n",
    "            if j == -1:\n",
    "                right = i\n",
    "                break\n",
    "            suffix[i] = j\n",
    "            j -= 1\n",
    "        ans = inf    \n",
    "        for i in range(left):\n",
    "            j = bisect_left(suffix, prefix[i] + 1)\n",
    "            if ans >  j - i - 1:\n",
    "                ans = j - i - 1\n",
    "        ans = min(ans, n - left, right + 1)\n",
    "        return ans if ans < inf else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*(n+1)\n",
    "        m = len(t)\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            if j<m and s[i] == t[j]:\n",
    "                j += 1\n",
    "            pre[i+1] = j\n",
    "        if j == m:\n",
    "            return 0\n",
    "        \n",
    "        post = [0] * (n + 1)\n",
    "        j = m-1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            post[i] = m-1-j\n",
    "        return min(m-pre[i]-post[i] for i in range(n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        sn,tn=len(s),len(t)\n",
    "        left,right=[0]*(sn+1),[0]*(sn+1)\n",
    "        # left 和 right 表示 s 的前后缀分别那覆盖 t 多少字符\n",
    "        cnt=0\n",
    "        ti=0\n",
    "        for si in range(sn):\n",
    "            if ti<tn and s[si]==t[ti]:\n",
    "                ti+=1\n",
    "                cnt+=1\n",
    "            left[si+1]=cnt\n",
    "        cnt=0\n",
    "        ti=tn-1\n",
    "        for si in range(sn-1,-1,-1):\n",
    "            if ti>=0 and s[si]==t[ti]:\n",
    "                ti-=1\n",
    "                cnt+=1\n",
    "            right[si]=cnt\n",
    "        ans=tn\n",
    "        for i in range(sn+1):\n",
    "            ans=min(ans,max(0,tn-(left[i]+right[i])))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        ns = len(s)\n",
    "        nt = len(t)\n",
    "        diff = [0]*(ns)+[nt]\n",
    "        fi = 0\n",
    "        bj = nt-1\n",
    "        for i in range(ns):\n",
    "            j = ns-1-i\n",
    "            if bj == -1:\n",
    "                pass\n",
    "            elif s[j]==t[bj]:\n",
    "                bj-=1\n",
    "            diff[j]+=bj+1\n",
    "            if fi == nt:\n",
    "                pass\n",
    "            elif s[i]==t[fi]:\n",
    "                fi+=1\n",
    "            diff[i+1]-=fi\n",
    "        # print(diff)\n",
    "        return max(min(diff),0)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        ns = len(s)\n",
    "        nt = len(t)\n",
    "        diff = [0]*(ns)+[nt]\n",
    "        fi = 0\n",
    "        bj = nt-1\n",
    "        for i in range(ns):\n",
    "            j = ns-1-i\n",
    "            if bj == -1:\n",
    "                pass\n",
    "            elif s[j]==t[bj]:\n",
    "                bj-=1\n",
    "            diff[j]+=bj+1\n",
    "            if fi == nt:\n",
    "                pass\n",
    "            elif s[i]==t[fi]:\n",
    "                fi+=1\n",
    "            diff[i+1]-=fi\n",
    "        # print(diff)\n",
    "        return max(min(diff),0)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        left, right = [inf] * n, [-1] * n\n",
    "        idx = m - 1\n",
    "        for r in range(n - 1, -1, -1):\n",
    "            while idx >= 0 and s[idx] != t[r]:\n",
    "                idx -= 1\n",
    "            if idx == -1:\n",
    "                break\n",
    "            right[r] = idx\n",
    "            idx -= 1\n",
    "        idx = 0\n",
    "        for l in range(n):\n",
    "            while idx < m and s[idx] != t[l]:\n",
    "                idx += 1\n",
    "            if idx == m:\n",
    "                break\n",
    "            left[l] = idx\n",
    "            idx += 1\n",
    "        if left[0] <= right[0]:\n",
    "            return 0\n",
    "\n",
    "        flag = inf\n",
    "        def check(ln):\n",
    "            nonlocal flag\n",
    "            if right[ln] != -1 or left[n - ln - 1] != inf:\n",
    "                return True\n",
    "            for i in range(1, n - ln):\n",
    "                if right[i + ln] > left[i - 1]:\n",
    "                    flag = i\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        low, high = 0, n - 1\n",
    "        ans = n\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                high = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n = len(s)\n",
    "        pre = [0]*(n+1)\n",
    "        suf = [len(t)-1]*(n+1)\n",
    "\n",
    "        j = 0\n",
    "        for i in range(1, n+1):\n",
    "            if j < len(t) and s[i-1] == t[j]:\n",
    "                j += 1\n",
    "            pre[i] = j\n",
    "\n",
    "        j = len(t)-1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if j >= 0 and s[i] == t[j]:\n",
    "                j -= 1\n",
    "            suf[i] = j\n",
    "\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(n+1):\n",
    "            ans = min(ans, max(0, suf[i]-pre[i]+1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        lenT, lenS = len(t), len(s)\n",
    "        inf = float('inf')\n",
    "        leftOffs = [inf]*lenT\n",
    "        rightOffs = [float('-inf')]*lenT\n",
    "        leftOff, rightOff = 0, lenT - 1\n",
    "        for i, cl in enumerate(s):\n",
    "            if leftOff < lenT and cl == t[leftOff]:\n",
    "                leftOffs[leftOff] = i\n",
    "                leftOff += 1\n",
    "            if rightOff >= 0 and s[lenS - 1 - i] == t[rightOff]:\n",
    "                rightOffs[rightOff] = lenS - 1 - i\n",
    "                rightOff -= 1\n",
    "        res = inf\n",
    "        # print(leftOffs, rightOffs)\n",
    "        r = 0\n",
    "        for l, pos in enumerate(chain([-1], leftOffs), -1):\n",
    "            if pos == inf: break\n",
    "            r = bisect_left(rightOffs, pos + 1, r)\n",
    "            if r - l - 1 > 0:\n",
    "                res = min(res, r - l - 1)\n",
    "            else:\n",
    "                return 0\n",
    "        return lenT if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m,n=len(s),len(t)\n",
    "        v=[-1]*n\n",
    "        j=m-1\n",
    "        for i in reversed(range(n)):\n",
    "            while j>=0 and s[j]!=t[i]:\n",
    "                j-=1\n",
    "            if j>=0 and s[j]==t[i]:\n",
    "                v[i]=j\n",
    "                j-=1\n",
    "        if v[0]>=0:\n",
    "            return 0\n",
    "        if n==1 or v[1]>=0:\n",
    "            return 1\n",
    "        l=[m]*n\n",
    "        j=0\n",
    "        for i in range(n):\n",
    "            while j<m and s[j]!=t[i]:\n",
    "                j+=1\n",
    "            if j<m and s[j]==t[i]:\n",
    "                l[i]=j\n",
    "                j+=1\n",
    "        # print(l,j)\n",
    "        # print(v)\n",
    "        ans=n\n",
    "        for i in range(n):\n",
    "            p=l[i-1] if i>0 else -1\n",
    "            if p==m:\n",
    "                break\n",
    "            v[i]=-1\n",
    "            j=bisect_right(v,p)\n",
    "            ans=min(ans,j-i)\n",
    "            # print(i,j,p,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        n,m = len(s),len(t)\n",
    "        left,right = [0]*(n+1),[0]*(n+1)\n",
    "        cnt = 0\n",
    "        zhizhen = 0\n",
    "        for i in range(n):\n",
    "            if zhizhen < m and s[i] == t[zhizhen]:\n",
    "                cnt += 1\n",
    "                zhizhen += 1\n",
    "            left[i+1] = cnt\n",
    "        \n",
    "        zhizhen = m - 1\n",
    "        cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if zhizhen >= 0 and s[i] == t[zhizhen]:\n",
    "                cnt += 1\n",
    "                zhizhen -= 1\n",
    "            right[i] = cnt\n",
    "        \n",
    "        ans = m\n",
    "        for k in range(n+1):\n",
    "            ans = min(ans,max(0,m - (left[k] + right[k])))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        idx = 0\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        left = [m] * n\n",
    "        for i in range(n):\n",
    "            ch = t[i]\n",
    "            while idx < m:\n",
    "                if s[idx] == ch:\n",
    "                    left[i] = idx\n",
    "                    idx += 1\n",
    "                    break\n",
    "                idx += 1\n",
    "            if idx == m:\n",
    "                break\n",
    "        \n",
    "        right = [-1] * n\n",
    "        idx = m - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ch = t[i]\n",
    "            while idx >= 0:\n",
    "                if s[idx] == ch:\n",
    "                    right[i] = idx\n",
    "                    idx -= 1\n",
    "                    break\n",
    "                idx -= 1\n",
    "            if idx == -1:\n",
    "                break\n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        ret = bisect_right(right, -1)\n",
    "        for i in range(n):\n",
    "            if left[i] == m:\n",
    "                break\n",
    "            j = bisect_right(right, left[i], i + 1)\n",
    "\n",
    "            ret = min(ret, j - i - 1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        f = [-1] * (n+2)\n",
    "        g = [-1] * (n+2)\n",
    "        j = 1\n",
    "        f[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            while j <= m and s[j-1] != t[i-1]:\n",
    "                j+=1\n",
    "            if j <= m:\n",
    "                f[i] = j \n",
    "                j+=1\n",
    "            else:\n",
    "                f[i] = -1\n",
    "        j = m\n",
    "        g[n+1] = m+1\n",
    "        for i in range(n, 0, -1):\n",
    "            while j > 0 and s[j-1] != t[i-1]:\n",
    "                j-=1\n",
    "            if j > 0:\n",
    "                g[i] = j \n",
    "                j-=1\n",
    "            else:\n",
    "                g[i] = -1\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(1, n - x + 2):\n",
    "                l = i - 1\n",
    "                r = i + x \n",
    "                if f[l] == -1 or g[r] == -1:\n",
    "                    continue \n",
    "                if f[l] < g[r]:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        head, tail = 0, n \n",
    "        while head < tail:\n",
    "            mid = (head + tail) >> 1\n",
    "            if check(mid):\n",
    "                tail = mid \n",
    "            else:\n",
    "                head = mid + 1\n",
    "        return head \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumScore(self, s: str, t: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        m = len(t)\r\n",
    "        # pre[i] := maximum length such that t[:pre[i]] is subsequence of s[:i]\r\n",
    "        # suf[i] := maximum length such that t[m - suf[i]:] is subsequence of s[i:]\r\n",
    "        pre = [0] * (n + 1)\r\n",
    "        suf = [0] * (n + 1)\r\n",
    "        j = 0\r\n",
    "        for i in range(n):\r\n",
    "            pre[i + 1] = pre[i]\r\n",
    "            if j < m and s[i] == t[j]:\r\n",
    "                pre[i + 1] += 1\r\n",
    "                j += 1\r\n",
    "        j = m - 1\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            suf[i] = suf[i + 1]\r\n",
    "            if j >= 0 and s[i] == t[j]:\r\n",
    "                suf[i] += 1\r\n",
    "                j -= 1\r\n",
    "        \r\n",
    "        return max(0, m - max(pre[i] + suf[i] for i in range(n + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        lenT, lenS = len(t), len(s)\n",
    "        inf = float('inf')\n",
    "        leftOffs = [inf]*lenT\n",
    "        rightOffs = [float('-inf')]*lenT\n",
    "        leftOff, rightOff = 0, lenT - 1\n",
    "        for i, cl in enumerate(s):\n",
    "            if leftOff < lenT and cl == t[leftOff]:\n",
    "                leftOffs[leftOff] = i\n",
    "                leftOff += 1\n",
    "            if rightOff >= 0 and s[lenS - 1 - i] == t[rightOff]:\n",
    "                rightOffs[rightOff] = lenS - 1 - i\n",
    "                rightOff -= 1\n",
    "        res = inf\n",
    "        # print(leftOffs, rightOffs)\n",
    "        for l, pos in enumerate(chain([-1], leftOffs), -1):\n",
    "            if pos == inf: break\n",
    "            r = bisect_left(rightOffs, pos + 1)\n",
    "            if r - l - 1 > 0:\n",
    "                res = min(res, r - l - 1)\n",
    "            else:\n",
    "                return 0\n",
    "        return lenT if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        '''\n",
    "        有思路后借助样例分析代码应该i如何实现\n",
    "        suf[i]表示s[i:]能够匹配t[suf[i]:]\n",
    "\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        n=len(s)\n",
    "        m=len(t)\n",
    "        suf=[m]*(n+1) #有些数组开+1很有好处，特别是一些对于下标有+1和-1需求的\n",
    "        #双指针j\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>=0 and s[i]==t[j]:\n",
    "                suf[i]=j  \n",
    "                j-=1\n",
    "            suf[i]=j+1  \n",
    "        ans=suf[0]  #借助样例得到的结论\n",
    "        if ans==0: return 0  \n",
    "        j=0 #枚举前缀\n",
    "        for i,c in enumerate(s):\n",
    "            if c==t[j]: #j=m代表了t就是s的子序列，这在上面已经判断过了\n",
    "                j+=1\n",
    "                ans=min(ans,suf[i+1]-j)\n",
    "        return ans\n",
    "        '''\n",
    "\n",
    "        #比较独特的思想是二分删除的长度，其实这个或许更有可能是可以想到的方法，可惜当时没有想到\n",
    "        n,m=len(s),len(t)\n",
    "        f=[n]*m #也可以试着用inf\n",
    "        g=[-1]*m    \n",
    "        j=0\n",
    "        for i in range(n):\n",
    "            if j<m and s[i]==t[j]:\n",
    "                f[j]=i\n",
    "                j+=1\n",
    "        j=m-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if j>-1 and s[i]==t[j]:\n",
    "                g[j]=i\n",
    "                j-=1 \n",
    "        def check(k:int)->bool:\n",
    "            #k是t中要删除的长度\n",
    "            if k==0:\n",
    "                if f[m-1]<n:return True\n",
    "                else:return False\n",
    "            if k==m:return True\n",
    "            for i in range(m-k+1):#i枚举合法删除位置的下标\n",
    "                if i==0:\n",
    "                    if g[i+k]>=0:return True\n",
    "                elif i==m-k:\n",
    "                    if f[i-1]<n:return True\n",
    "                elif f[i-1]<g[i+k] :return True  \n",
    "            return False\n",
    "        left,right=-1,m+1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                right=mid  \n",
    "            else:\n",
    "                left=mid  \n",
    "        return right\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, s: str, t: str) -> int:\n",
    "        m = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            m[c].append(i)\n",
    "\n",
    "        n = len(t)\n",
    "        prev = [len(s)] * n\n",
    "        start = 0\n",
    "        for idx, c in enumerate(t):\n",
    "            m_c_idx = bisect_left(m[c], start)\n",
    "            if m_c_idx < len(m[c]):\n",
    "                prev[idx] = m[c][m_c_idx]\n",
    "                start = m[c][m_c_idx] + 1\n",
    "            else:\n",
    "                break\n",
    "        #print(prev)\n",
    "\n",
    "        \n",
    "        suffix = [-1] * n\n",
    "        end = len(s)\n",
    "        for idx in range(n-1, -1, -1):\n",
    "            c = t[idx]\n",
    "            m_c_idx = bisect_left(m[c], end) - 1\n",
    "            if m_c_idx >= 0:\n",
    "                suffix[idx] = m[c][m_c_idx]\n",
    "                end = m[c][m_c_idx]\n",
    "            else:\n",
    "                break\n",
    "        #print(suffix)\n",
    "            \n",
    "\n",
    "        def valid(length):\n",
    "            if length >= len(t):\n",
    "                return True\n",
    "            j = 0\n",
    "            for i in range(length, len(t)):\n",
    "                if suffix[i]>-1 and (suffix[i] > (prev[j-1] if j-1>=0 else -1)) and (prev[j-1] != n if j - 1 >= 0 else True):\n",
    "                    #print(f'valid in {j=} {i=}')\n",
    "                    return True\n",
    "                else:\n",
    "                    j += 1\n",
    "            #print(f'{j=}')\n",
    "            return prev[j-1] < len(s)\n",
    "\n",
    "        lo, hi = 0, len(t)+1\n",
    "        while lo < hi:\n",
    "            mi = (lo + hi) // 2\n",
    "            if not valid(mi):\n",
    "                lo = mi+1\n",
    "            else:\n",
    "                hi = mi\n",
    "        return lo"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
